Many data processing systems require large amounts of data storage space and are configured in a hierarchical manner. More frequently accessed data is stored in high speed but expensive memory, such as in direct access storage devices (DASD), while less frequently accessed data is stored in slower speed but less expensive memory, such as on tape media in automated storage libraries. One such system is a virtual tape system (VTS) in which logical volumes, sometimes numbering in the hundreds of thousands, are written to tape cartridges. As illustrated in FIG. 1, a logical volume may be stored entirely in a single cartridge (such as logical volume X being stored in cartridge A) or may span two or more cartridges (such as logical volume Y being stored in cartridges A and B). When a volume is added to the library, it is assigned an “order” in a “scratch” category. New orders are appended sequentially to the end of the scratch category. FIGS. 2A and 2B illustrate a new volume F being added to the end of the scratch category as order 73. When data is to be written to a volume, the volume is moved to a “private” category and assigned a new order appended to the end of the private category. FIGS. 3A and 3B illustrate two volumes F and G being added to the end of the private category as orders 104 and 105, respectively.
For any of a variety of reasons, data in a volume may no longer be needed and the volume is moved back from the private category to a scratch category, again being assigned a new order appended to the end of the scratch category.
When a volume is moved from one category to another (from scratch to private or from private to scratch), a vacancy is left in the sequence of orders. In FIGS. 3A and 3B, vacancies are left in the scratch category between orders 72 and 74 and between orders 241 and 243 when volumes F and G are moved to the private category. The vacated orders in a category are never reassigned and consequently the orders in the categories may quickly fragment. When the number of volumes in a VTS is in the hundreds of thousands, the number of orders may reach the millions on a busy system. The large number of vacant orders may significantly compromise performance of the database.